package com.example.demo.leetcode.zuocheng.btree;

import java.util.HashMap;
import java.util.LinkedList;

import javax.sound.sampled.Line;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/8/28 14:28
 */
public class Tree_二叉树最大宽度 {


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    // 求一个二叉树的最大宽度
    // curLevel  遍历的当前层数
    // curLevelNodes 遍历的当前层数的节点数
    // 维护一个map 存放 节点-层数， 每次节点的层数和当前层数比较，想等，当前层数节点数+1，不相等，结算一次max
    // max 最大宽度
    public static int getWidthFromTree(TreeNode root){

        //使用队列 每次出来的都是同一层的数据，处理完一层的，重置curLevelNodes=1 后处理下一层的。
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int curLevel = 1;
        int curLevelNodes = 0;
        int max = 0;
        HashMap<TreeNode,Integer> nodeLevelMap = new HashMap<>();
        nodeLevelMap.put(root,1);

        while(!list.isEmpty()){
            TreeNode poll = list.poll();
            Integer curNodeLevel = nodeLevelMap.get(poll);

            if(poll.left!=null){
                list.add(poll.left);
                nodeLevelMap.put(poll.left,curLevel+1);
            }
            if(poll.right!=null){
                list.add(poll.right);
                nodeLevelMap.put(poll.right,curLevel+1);
            }
            //节点层数 和 当前层数想等
            if(curNodeLevel == curLevel){
                curLevelNodes++;
            }else{
                curLevel++;
                max = Math.max(curLevelNodes,max);
                curLevelNodes=1;
            }
        }
        max = Math.max(curLevelNodes,max);
        return max;
    }

    public static void main(String[] args) {

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.left=treeNode2;treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;treeNode3.right=treeNode7;

        System.out.println(getWidthFromTree(treeNode1));
    }


}
